{F1;F2;F3;[C;<N;αWINGED EDGE.;λ30;P16;I425,0;JC;FA}     SECTION 2.
{JC;FD}         THE WINGED EDGE POLYHEDRON REPRESENTATION.
{λ10;W250;JA;FA}
	2.0	Introduction to the Winged Edge.
	2.1	Winged Edge Link Fields.
	2.2	Perimeter Accessing.
	2.3	Lowest Level Polyhedron Synthesis and Alteration.
	2.4	Edge and Face Splitting.
	2.5	Coordinate Free Polyhedron Representation.

{λ30;W0;I950,0;JU}
[2.0	Introduction to the Winged Edge.]

	In this  chapter,  a  particular computer  representation for
polyhedra  is presented and  some of  its virtues and faults are  explained. The
representation is implemented as  a data structure composed of  small
blocks of words containing pointers and  data in the fashion usual to
graphics  and simulation. An  introduction to such data  structures can be
found in Knuth  (Art of Computer  Programming, chapter 2, volume  I).
Quickly  reviewing   Knuth's  terminology:  a  node  is   a  group  of
consecutive words of memory, a field is a named portion of a node and
a link is  the absolute machine address  of a node. The  notation for
referring  to a  field of a  node consists  simply of the  field name
followed by a  link expression enclosed  in parentheses. For  example,
the two faces of an edge node  whoes link is stored in the variable named
"edge", are found in the fields named NFACE and PFACE, and are referred
to as NFACE(edge) and  PFACE(edge).  Although my latest  language of
implementation is  PDP-10 machine code, examples will be given in a
fictional programming language which combines ALGOL
with Knuthian node/link notation.{Q}
{H7;O0,630,700;
L0,-20,0*5,-61*5;L0,20,0*5,61*5;
L-86*5,83*5,0*5,61*5,86*5,83*5;L-86*5,-83*5,0*5,-61*5,86*5,-83*5;
H2;
L42*5,106*5,86*5,83*5,126*5,0*5,86*5,-83*5,42*5,-106*5,-42*5,-106*5;
L-42*5,-106*5,-86*5,-83*5,-126*5,0*5,-86*5,83*5,-42*5,106*5,42*5,106*5;

L-30,-10;FB	}edge
{L-380,-10;	}NFACE(edge)
{L240,-10;	}PFACE(edge)
{L-70,-370;	}NVT(edge)
{L-70,350;	}PVT(edge)
{L-360,320;	}NCCW(edge)
{L-390,-360;	}NCW(edge)
{L220,320;	}PCW(edge)
{L260,-360;	}PCCW(edge)

{I1300,0;O0,630,950;
λ10;JC;FA}  [FIGURE 2.1 - Winged Edge Topology.]

The orientation of links is as viewed from the exterior side of the surface.
The eight mnemonics in the figure, were derived as follows:
	NFACE(edge)	Negative Face of edge.
	PFACE(edge)	Positive Face of edge.
	PVT(edge)		Positive Vertex of edge.
	NVT(edge)		Negative Vertex of edge.
	NCW(edge)		edge in Negative face Clockwise from edge.
	PCW(edge)		edge in Positive face Clockwise from edge.
	NCCW(edge)		edge in Negative face Counter Clockwise from edge.
	PCCW(edge)		edge in Positive face Counter Clockwise from edge.{λ30;FA}
{Q}
[2.1	Winged Edge Link Fields.]

	A polyhedron  in  made up  of four  kinds  of nodes:  bodies,
faces, edges and  vertices. The body node is the head of three rings:
a ring of  faces, a ring  of edges and  a ring  of vertices. In  this
context, a ring is a doubly linked circular list  with a head node.
Each  face  and  each  vertex  points at  only one  of  the  edges  on its
perimeter. Each edge  points at its two  faces and its two  vertices.
Completing the  topology, each edge node  contains a link  to each of
its four immediate neighboring edges clockwise and counter  clockwise
about its face perimeters as seen from the  exterior side of the surface
of the  polyhedron. These last four links are  the wings of the edge,
which provide  the  basis for  efficient  face perimeter  and  vertex
perimeter accessing. Finally,    the links  of  the edge  nodes  can be
consistently oriented with respect  to the surface of  the polyhedron
so that the surface always has two sides: the inside and the outside.

	Observe that  there are twenty-two  link fields in  the basic
representation: bodies contain six links, faces three links, vertices
three links and edges ten links. If we allow a link name such  as PED
to serve different  roles depending on whether it applies  to a body,
face, edge or vertex; then the minimum number of different link field
names that need to be coined is ten. The data structures and the link
fields comprising  the structures are listed in  box (2.1) below. The
ten links names include: NFACE and PFACE for two fields that  contain
face links in  edges and the  face ring, NED  and PED for  two fields
that  contain edge links,   NVT and  PVT for two  fields that contain
vertex links, and NCW,  PCW, NCCW and PCCW  for the four fields  that
contain edge links and are called the wings.
{|;λ10;JA}
BOX 2.1    Data Structure				Link Names

	1. Face Ring of a Body.			NFACE	PFACE
	2. Edge Ring of a Body.			NED		PED
	3. Vertex Ring of a Body.			NVT		PVT
	4. First Edge of a Vertex.					PED
	5. First Edge of a Face.					PED
	6. The two faces of an edge:		NFACE	PFACE
	7. The two vertices of an edge:		NVT		PVT
	8. The four wing edges of an edge:	NCW  PCW  NCCW  PCCW
{|;λ30;JU}
	By constraining the arrangement of links in an edge node both
the  surface  orientataion  (interior  and  exterior)  and  a  linear
orientation of the edge as a directed vector can be encoded.   Figure
2.1 diagrams the arrangement of  the links comprising the topology of
an  edge of  a polyhedron  as viewed  from the  exterior side  of its
surface. Although  the vertices  in figure  2.1 are  shown with  only
three  edges,  vertices  may have  any  number  of  edges; the  other
potential edges would not  be directly linked to  the middle edge  of
the figure and  so were not  shown.  To complete  the representation,
space is  allocated to contain the 3-D  coordinates of each vertex in
fields named XWC,  YWC and ZWC;  the initials  "WC" stand for  <world
coordinates>.  Further important  (but not  fundamental) data  fields
include,  the 3-D  perspective projected  coordinates of  each vertex
with respect to a camera (one camera at a time)  in fields named XPP,
YPP,   ZPP of vertex nodes.   Faces on the other  hand carry exterior
pointing normal  vectors and  several  words of  photometric  surface
characteristics. The face  vectors are derived from  surface topology
and  vertex loci,   and so  are not basic  geometric data as  in some
representations. A specific winged edge node format of implementation
is given in appendix (**).

	The Winged  Edge polyhedron representation as  just presented
complete.  Edge nodes carry most of  the topology, vertex nodes carry
the geometry, face  nodes carry the  photometry and body nodes  carry
the semantics.   The point that remains to be  demonstrated,  is that
the appropriate subroutines for creating,  maintaining and exploiting
edge  orientation are  are  easily coded,    execute efficiently  and
provide good primitives for solving such geometric problems as hidden
line elimination and polyhedral intersection.

[2.2	Perimeter Accessing.]

	The perimeter of a face is an ordered list of edges and vertices,
the perimeter of a vertex is an ordered list of edges and faces, and the
perimeter of an edge is an ordered list consisting of exactly two faces
and two vertices. The perimeter definitions are caricatured in figure (2.2).
One virtue of the winged edge representation is that the perimeters can be
traveled in either direction (clockwise or counter clockwise) and are always
maintained in order.

	Given one edge of  a face (or vertex) perimeter,  the next edge
clockwise (or  counter  clockwise) from  the  given  edge  about  the
particular face (or vertex) can be retrieved  from the data  structure
with the assistance of two subroutines  called ECW and ECCW. The idea
of  the edge clocking routines  is to match the  given face (or vertex)
with one  of the faces  (or vertices) of  the given  edge and to  then
return the appropriate wing. A possible coding of ECCW and ECW might
be as follows:
{↓;JA;λ7;F3}
COMMENT FETCH EDGE CCW FROM E ABOUT FV;
INTEGER PROCEDURE ECCW (INTEGER E,FV);
BEGIN "ECCW"
	IF PFACE(E)=FV THEN RETURN(PCCW(E));
	IF NFACE(E)=FV THEN RETURN(NCCW(E));
	IF PVT(E)=FV   THEN RETURN(PCW(E));
	IF NVT(E)=FV   THEN RETURN(NCW(E));
	FATAL;
END "ECCW";
{↑;W670;JA;λ7;F3}
COMMENT FETCH EDGE CLOCKWISE FROM E ABOUT FV;
INTEGER PROCEDURE ECW (INTEGER E,FV);
BEGIN "ECW"
	IF PFACE(E)=FV THEN RETURN(PCW(E));
	IF NFACE(E)=FV THEN RETURN(NCW(E));
	IF PVT(E)=FV   THEN RETURN(NCCW(E));
	IF NVT(E)=FV   THEN RETURN(PCCW(E));
	FATAL;
END "ECW";
{W0;JUFA;λ30;}
	The first edge  of a face  or vertex is (of  course) directly
available from the  PED field of the face or vertex. For example, the
two code fragments below can be used to visit all the edges of a face or
or all the edges of a vertex, respectively.
{JA;↓;λ7;F3}
COMMENT APPLY FUNCTION TO EDGES OF A FACE;
BEGIN
	INTEGER F,E,E0;
	E←E0←PED(F);
	DO FUNCTION(E) UNTIL E0=(E←ECCW(E,F));
END;
{↑;W670;JA;λ7;F3}
COMMENT APPLY FUNCTION TO EDGES OF A VERTEX;
BEGIN
	INTEGER V,E,E0;
	E←E0←PED(V);
	DO FUNCTION(E) UNTIL E0=(E←ECCW(E,V));
END;
{JUFA;W0;λ30;}
	Using the same idea as in the  edge clocking routines, a face
or vertex can be  retrieved relative to a given edge and a given face
or vertex. These routines include: FCW and FCCW which return the face
clockwise or  counter clockwise from a  given edge with respect  to a
given  vertex;  VCW and  VCCW  which  return the  vetex  clockwise or
counter clockwise from a given edge with respect to a given face; and
OTHER which return the face  or vertex of the given edge opposite the
given face or vertex.  Together the seven routines: ECW, ECCW,   VCW,
VCCW, FCW,  FCCW  and OTHER exhaust the possible  oriented retrievals
from  an edge node; they  also alleviate the need  to ever explicitly
reference a wing  field when traveling the  surface of a  polyhedron.
With  node type  checking and  signed arguments  the seven  perimeter
accessing  routines could  be  replaced by  a single  routine perhaps
named PERIMETER_FETCH or PGET. On the otherhand, the proliferation of
accessing  names  declares  the  direction  and  node  type  for  for
assembling better in line code. {Q}
[2.3	Edge and Face Splitting.]

	Another simple virture  of the winged edge  representation is
that  edges and faces can  be split using subroutines  that make only
local alterations to the data structure; likewise,  the splits can be
easily removed since the doubly  linked rings allow rapid deletion of
nodes  from a body. The edge split  routine, ESPLIT, makes a new edge
and a new vertex and  places them into the surface topology  as shown
in  figure (2.3).    The kill  edge-vertex routine,  KLEV,  undoes an
ESPLIT.  The face split routine,  MKFE, creates a new edge and a  new
face and  places them into  the surface topology  as shown  in figure
(2.4); the kill face-edge routine, KLFE, undoes a MKFE.

{JA;H1;I∂5,1260;V∂0,0;I∂-5,0;λ10;
JA}FIGURE 2.3{JC} ESPLIT AND KLEV.
{I∂0,200;}VNEW ← ESPLIT(E);{I∂0,800;}E ← KLEV(VNEW);
{H3;X0.5;
	I∂180,315;	*FIG2.3A;
	I∂0,315+630;	*FIG2.3B;
	I∂275,0;
JA;H1;I∂5,1260;V∂0,0;I∂-5,0;λ10;
}FIGURE 2.4{JC} MKFE AND KLFE
{I∂0,200;}ENEW ← MKFE(V1,F,V2);{I∂0,800;}F ← KLFE(ENEW);
{H3;X0.5;
	I∂180,315;	*FIG2.4A;
	I∂0,315+630;	*FIG2.4B;
	I∂150,0;λ30;}

{JA;W300;λ10;F3}
INTEGER PROCEDURE ESPLIT (INTEGER E);
BEGIN "ESPLIT"
	INTEGER VNEW,ENEW,
COMMENT CREATE A NEW EDGE AND VERTEX ON THE BODY;
	VNEW ← MKV(E);
	ENEW ← MKE(E);
COMMENT CONNECT VERTICES AND FACES TO EDGES;
	PVT(ENEW) ← PVT(E);
	NVT(ENEW) ← VNEW;
	PVT(E) ← VNEW;
	PFACE(ENEW) ← PFACE(E);
	NFACE(ENEW) ← NFACE(E);
COMMENT CONNECT EDGES TO VERTICES;
	IF PED(V)=E THEN PED(V)←ENEW;
	PED(VNEW)←ENEW;
COMMENT LINK THE WINGS TOGETHER;
	NCW(ENEW) ← E; PCCW(ENEW) ← E;
	PCW(E) ← ENEW; PCCW(E) ← ENEW;
	WING(NCCW(E),ENEW);
	WING(PCW(E),ENEW);
	RETURN(VNEW);
END "ESPLIT";

{JU;W0;λ30;FA}

[2.4	Lowest Level Polyhedron Synthesis and Alteration.]

	This section concerns the details  of link manipulation which
are beneath the  Euler primitives explained in the next section.
The direct handling of links is not required of the  ordinary user
of winged  polyhedra, but is  discussed here  from the view  point of
implementation.  Internal  to  a modeling  system,  the  geometry and
topology  of   a  desired  polyhedron   becomes  available  in   some
non-standard format and a winged edge model is desired. Although bulk
conversion from an  alein external  polyhedron format  into a  winged
edge format is  occassionally important, the same details  apply when
altering an existing structure.

	In the  typical situation, there  are five steps:  first, get
the proper kinds of nodes into the body rings using the MKF, MKE, MKV
primitives. second, place the vertices by setting their XWC, YWC, ZWC
fields; third,  connect each vertex  and face  pointed to one  of its
edges  by setting their PED fields. fourth,  connect each edge to its
two faces and  its two vertices by  setting their NFACE, PFACE,  NVT,
PVT fields.  Finally, create the wing perimeter  pointers by applying
the WING primitive to pairs of edges to be mated.

{|;λ10;JA}
BOX {JC} LOWEST LEVEL WINGED EDGE ROUTINES.

 	MKB,MKF,MKE,MKV,MKFRAME.	Make body, face, edge, vertex or frame node.
	WING,INVERT,EVERT		Setup or change wing pointers.
	LINKED				Find whether two entities are linked.
	ECW,ECCW				Edge fetching around Face and Vertex perimeters.
	OTHER,VCW,VCCW,FCW,FCCW	Face/Vertex fetching from an edge.
	BDET,BATT,BGET			Body parts linking and body get.
{|;λ30;JU}

[2.5	Coordinate Free Polyhedron Representation.]

	As  in general  relativity,  all  geometric entities  can  be
represented  in a coordinate free  form.  In particular,   the vertex
coordinates of a  polyhedra can  be recovered from  edge lengths  and
dihedral angles  (the angle formed  by the  two faces at  each edge).
Having the  geometry carried by only two numbers per edge rather than
by three numbers per vertex does not necessarily yield a more concise
representation because  edges always outnumber vertices  two for one,
and in the case of a triangulated polyhedron edges outnumber vertices
by three to one.

	One application  of a  coordinate free representation  arises
when it is necessary to measure a complicated shape with simple tools
such as a caliper and straight edge. For example, one way to go about
recording the topology and geometry of an arbitrary object is to draw
a  triangulated  polyhedron  on  its  surface  with  serial  numbered
vertices and record  for each edge its  length, its two vertices  and
its <signed  dihedral length>.   The dihedral length  is the distance
between the vertices  opposite the  edge in  each of  the edge's  two
triangles, the  length can  be given  a sign  convention to  indicate
whether the edge  is concave or convex.  The required dihedral angles
can then be computed from the signed dihedral lengths.